package com.wl2o2o.lanqiao.xzfourteen;

/**
* @author : WLei224
* @date ：2023年4月2日 上午12:36:55 
* 
*/
//1:无需package
//2: 类名必须Main, 不可修改

public class kuaisumi{
	
	 public static void main(String[] args){
		 
		 System.out.println(abmodp1(2, 10, 131));
		 
		 int ans = 1;
		 int a = 2;
		 int b = 10;
	     int p = 131;
	     while(b > 0){
	         if((b&1) != 0)ans = ans * a % p;//b是偶数
	         b = b >> 1;
	         a = a*a%p;
	     }
	     /***
	      * 仅测试API使用如下代码，与本文件内容无关
	      */
//	     int[] num = {1,3,4,5,6,7,8,9};
//	     String[] strings = new String[10];
//	     for(int i  = 0; i< num.length; i++) {
//	    	 strings[i] = num[i]+"";
//	     }
//	     System.out.println(Arrays.toString(strings));
	     
	     System.out.println(ans);
	 }

	 //快速幂
	 public static int abmodp1(int a, int b, int p){
	     //扩底降幂
	     /**
	     * a^9 = a * a^8
	     * a^8 = a^2^4
	     */
	     int ans = 1;
	     while(b > 0){
	
	         if(b % 2 == 0){
	             a = (a * a) % p;
	             b = b/2;
	         } else {
	             b = b-1;
	             ans = ans * a % p;
	             a = a * a % p;
	             b = b /2 ; 
	         }
	         ans = ans * a % p;
	         a = a * a % p;
	         b = b/2;
	     }
	     return ans;
	 }
	//对方法一进行的优化
	 public static int abmodp2(int a, int b, int p){
	     int ans = 1;
	     while(b > 0){
	
	         if(b % 2 ==1)ans = ans * a % p;
	         a = a * a % p;
	         b = b/2;
	     }
	     return ans;
	 }
	 
	 
 

 //
}
